/**
 * 这是 LeetCode 第 55. 跳跃游戏 的解决方案
 * https://leetcode.cn/problems/jump-game
 */
class JumpGame {
    /**
     * 方法：贪心算法 - 正向查找
     * 
     * 功能：判断是否能从数组第一个位置跳到最后一个位置
     * 
     * 实现逻辑：
     * 1. 维护一个变量max表示能够到达的最远位置
     * 2. 遍历数组，在每个位置i：
     *    - 如果i超过了max，说明无法到达该位置，返回false
     *    - 更新max为当前能到达的最远位置max和(i + nums[i])中的较大值
     *    - 如果max已经可以到达或超过最后一个位置，返回true
     * 
     * 时间复杂度：O(n)，其中n为数组长度
     * 
     * 空间复杂度：O(1)，只使用常数额外空间
     */
    public boolean canJump(int[] nums) {
        int len = nums.length;
        int max = 0;
        for(int i = 0; i < len; i++){
            if(i > max){
                return false;
            }
            max = Math.max(max, i + nums[i]);
            if(max >= len - 1){
                return true;
            }
        }
        return false;
    }

    /**
     * 方法：贪心算法 - 反向查找
     * 
     * 功能：判断是否能从数组第一个位置跳到最后一个位置
     * 
     * 实现逻辑：
     * 1. 从倒数第二个位置向前遍历
     * 2. 对于每个位置i，检查是否能跳到last位置：
     *    - 如果从i能跳到last（i + nums[i] >= last），则更新last为i
     * 3. 最后检查last是否为0，如果是则说明能从起点跳到终点
     * 
     * 时间复杂度：O(n)，其中n为数组长度
     * 
     * 空间复杂度：O(1)，只使用常数额外空间
     */
    public boolean canJumpLast(int[] nums) {
        int len = nums.length;
        int last = len - 1;
        for(int i = len - 2; i >= 0; --i){
            if(i + nums[i] >= last){
                last = i;
            }
        }
        return last == 0;
    }
}